In a store-and-forward telecommunications network, each network node passes protocol data units to the next node, in bucket-brigade fashion, until the protocol data units arrive at their final destination. A network node can have a variety of names (e.g. “switch,” “router,” “access point,” etc.) and can perform a variety of functions, but it always has the ability to receive a protocol data unit on one input link and transmit it on one or more output links. FIG. 1 depicts a block diagram of the salient components of a typical network node in the prior art.
For the purposes of this specification, a “protocol data unit” is defined as the data object that is exchanged by entities. Typically, a protocol data unit exists at a layer of a multi-layered communication protocol and is exchanged across one or more network nodes. A “frame,” a “packet,” and a “datagram” are typical protocol data units.
In some cases, a protocol data unit might spend a relatively brief time in a network node before it is processed and transmitted on an output link. In other cases, a protocol data unit might spend a long time.
One reason why a protocol data unit might spend a long time in a network node is because the output link on which the protocol data unit is to be transmitted is temporarily unavailable. Another reason why a protocol data unit might spend a long time in a network node is because a large number of protocol data units arrive at the node faster than the node can process and output them.
Under conditions such as these, a network node typically stores or “queues” a protocol data unit until it is transmitted. Sometimes, the protocol data units are stored in an “input queue” and sometimes the protocol data units are stored in an “output queue.” An input queue might be employed when protocol data units arrive at the network node (in the short run) more quickly than they can be processed. An output queue might be employed when protocol data units arrive and are processed (in the short run) more quickly than they can be transmitted on the output link.
A queue has a finite capacity, and, therefore, it can fill up with protocol data units. When a queue is filled, the attempted addition of protocol data units to the queue causes the queue to “overflow” with the result that the newly arrived protocol data units are discarded or “dropped.” Dropped protocol units are forever lost and do not leave the network node.
A network node that comprises a queue that is dropping protocol data units is called “congested.” For the purposes of this specification, a “congestible node” is defined as a network node (e.g. a switch, router, access point, etc.) that is susceptible to dropping protocol data units.
The loss of a protocol data unit has a negative impact on the intended end user of the protocol data unit, but the loss of any one protocol data unit does not have the same degree of impact as every other protocol data unit. In other words, the loss of some protocol data units is more injurious than the loss of some other protocol data units.
When a node is congested, or close to becoming congested, it can be prudent for the node to intentionally and proactively drop one or more protocol data units whose loss will be less consequential than to allow arriving protocol data units to overflow and be dropped and whose loss might be more consequential. To accomplish this, the node can employ an algorithm to intelligently identify:                (1) which protocol data units to drop,        (2) how many protocol data units to drop, and        (3) when to drop those protocol data units,in order to:        (a) reduce injury to the affected communications, and        (b) lessen the likelihood of congestion in the congestible node.One example of an algorithm to mitigate congestion in congestible nodes is the well-known Random Early Detection algorithm, which is also known as the Random Early Discard Algorithm.        
Some legacy nodes, however, were not designed to intentionally drop a protocol data unit and it is often technically or economically difficult to retrofit them to add that functionality. Furthermore, it can be prohibitively expensive to build nodes that have the computing horsepower needed to run an algorithm such as Random Early Discard or Random Early Detection.
Therefore, the need exists for a new technique for ameliorating the congestion in network nodes without some of the costs and disadvantages associated with techniques in the prior art.